To sign with RSA, one usually encodes the message m as p(m) and then raises the result,to the private exponent modulo N. In Asiacrypt 2000, Coron et al. showed how to build a secure RSA encoding scheme mu'(m) for signing arbitrarily long messages from a secure encoding scheme mu(m) capable of handling only fixed-size messages, without making any additional assumptions. However, their construction required that the input size of mu be larger than the modulus size. In this paper we-present a construction for which the input size of mu does not have to be larger than N. Our construction shows that the difficulty in building a secure encoding for RSA signatures is not in handling messages of arbitrary length, but rather in finding a secure encoding function for short messages, which remains an open problem in the standard model.
展开▼
